package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.HashSet;
import java.util.Set;

/**
 * 描述：
 * 给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。
 * <p>
 * 返回 n 的长度。如果不存在这样的 n ，就返回-1。
 * <p>
 * 注意： n 不符合 64 位带符号整数
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/smallest-integer-divisible-by-k
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 🧑 ‍wanwei
 * @since 2023-01-16 15:25
 */
public class CU1015 {
    public static void main(String[] args) {
        //暴力破解: 一直累加直到 出现一个全是1的数 直到超过范围 这个太耗时了
        //直接用全为1的数去除 最多64次即可得出结果
        //System.out.println(new BigInteger("1111111111111111111111"));

        System.out.println(smallestRepunitDivByK(3));

    }

    /**
     * 由于数值类型表示的值有限制 所以可以将数表示 (n * 10 + 1) 累加 从n为1开始往上累加
     *
     * 将每个位的数与k相除取余 直到余数为0 如果余数重复 则说明之前已经计算过 则可以直接退出 返回-1 不退出就是无限循环
     *
     * @param k
     * @return
     */
    public static int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) {
            return -1;
        }
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 1, remainder = 1 % k; set.add(remainder); i++, remainder = (remainder * 10 + 1) % k) {
            if (remainder == 0) {
                return i;
            }
        }
        return -1;
    }
}
